import java.util.Stack;

// 定义单链表节点类
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class AddTwoNumbers {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 步骤1：使用栈存储两个链表的数字
        // 栈可以让我们从右向左处理数字，同时不修改输入链表
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();

        // 将链表l1的数字压入stack1
        ListNode current = l1;
        while (current != null) {
            stack1.push(current.val);
            current = current.next;
        }

        // 将链表l2的数字压入stack2
        current = l2;
        while (current != null) {
            stack2.push(current.val);
            current = current.next;
        }

        // 步骤2：从栈中取出数字进行加法运算
        int carry = 0; // 进位
        ListNode dummy = new ListNode(0); // 虚拟头节点
        ListNode head = dummy;

        // 当任一栈不为空或有进位时继续处理
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            // 从栈中获取数字，若栈为空则用0
            int x = stack1.isEmpty() ? 0 : stack1.pop();
            int y = stack2.isEmpty() ? 0 : stack2.pop();

            // 计算当前位之和及新的进位
            int sum = x + y + carry;
            carry = sum / 10; // 计算进位
            int digit = sum % 10; // 当前位的数字

            // 创建新节点并插入到结果链表头部
            ListNode newNode = new ListNode(digit);
            newNode.next = head.next;
            head.next = newNode;
        }

        // 步骤3：返回结果链表（跳过虚拟头节点）
        return dummy.next;
    }

    // 辅助方法：从数组创建链表（用于测试）
    public static ListNode createList(int[] arr) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for (int val : arr) {
            current.next = new ListNode(val);
            current = current.next;
        }
        return dummy.next;
    }

    // 辅助方法：打印链表（用于测试）
    public static void printList(ListNode head) {
        System.out.print("[");
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) System.out.print(",");
            head = head.next;
        }
        System.out.println("]");
    }

    // 主方法：测试用例
    public static void main(String[] args) {
        AddTwoNumbers solution = new AddTwoNumbers();

        // 测试用例1：l1 = [7,2,4,3], l2 = [5,6,4]
        ListNode l1 = createList(new int[]{7,2,4,3});
        ListNode l2 = createList(new int[]{5,6,4});
        System.out.print("测试用例1 输入: l1=");
        printList(l1);
        System.out.print("              l2=");
        printList(l2);
        System.out.print("输出: ");
        printList(solution.addTwoNumbers(l1, l2));

        // 测试用例2：l1 = [2,4,3], l2 = [5,6,4]
        l1 = createList(new int[]{2,4,3});
        l2 = createList(new int[]{5,6,4});
        System.out.print("测试用例2 输入: l1=");
        printList(l1);
        System.out.print("              l2=");
        printList(l2);
        System.out.print("输出: ");
        printList(solution.addTwoNumbers(l1, l2));

        // 测试用例3：l1 = [0], l2 = [0]
        l1 = createList(new int[]{0});
        l2 = createList(new int[]{0});
        System.out.print("测试用例3 输入: l1=");
        printList(l1);
        System.out.print("              l2=");
        printList(l2);
        System.out.print("输出: ");
        printList(solution.addTwoNumbers(l1, l2));
    }
}
